Round Robin (RR) is a well-known strategy for scheduling multiple requests for a common resource, see e.g. “Operating Systems—a Modern Perspective” by G. Nutt, 2nd edition, published by Addison Wesley Higher, Jul. 18, 2001. If there are K contenders for a resource then RR allocates the resource to each of the contenders for a fixed duration (called time slice) at a time. When the time slice allocated to the current contender “i” is over, the resource is allocated to the next contender “i+1” and so on. The allocation of the resource is performed in a circular fashion. It is allocated to contender 1 first followed by 2 and so on. When the time slice for contender K is over, the resource is allocated to contender 1 again. At a given point in time, the contenders for a resource may or may not be ready for using the resource. If a resource is allocated to a contender when its turn arrives, irrespective of whether or not the contender is ready, the strategy is called non-work-conserving round robin; whereas if a resource is allocated to a contender if and only if it is ready, the strategy is called a work-conserving round robin.
RR has been used in a number of different situations including switching of data arriving at multiple queues to a common outgoing port. A typical implementation of such an RR strategy is based on the well-known priority encoder principle (also known as daisy chaining principle), see e.g. “Digital Design Principles and Practices 2nd Edition” by John F. Wakerly published in 1994 and 1990, Prentice-Hall, Inc. Englewood Cliffs, N.J. However the delay achieved with such an approach is directly proportional to the number of contenders. Thus the delay achieved with a high number of queues that are to be multiplexed to an outgoing port may become too high for use in a high-speed data switching system.